#include <vector>

using namespace std;

void adjustDown(vector<int> &array, int n, int parent)
{
    int child = 2 * parent + 1;
    while (child < n)
    {
        if (child + 1 < n && array[child + 1] > array[child])
        {
            child++;
        }
        if (array[child] > array[parent])
        {
            swap(array[child], array[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(vector<int> &array)
{
    int n = array.size();
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        adjustDown(array, n, i);
    }
    int end = n - 1;
    while(end > 0)
    {
        swap(array[0], array[end]);
        adjustDown(array, end, 0);
        end--;
    }

}